#!/usr/bin/env python
#
# Grid metascheduler for routing jobs to sites according to a ranking
# algorithm
#
# Author:   Mike Murphy <mamurph@cs.clemson.edu>
# Revision: 23 September 2009
#
#   Copyright 2009 Clemson University
#
#   Licensed under the Apache License, Version 2.0 (the "License");
#   you may not use this file except in compliance with the License.
#   You may obtain a copy of the License at
#
#       http://www.apache.org/licenses/LICENSE-2.0
#
#   Unless required by applicable law or agreed to in writing, software
#   distributed under the License is distributed on an "AS IS" BASIS,
#   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#   See the License for the specific language governing permissions and
#   limitations under the License.
#
# This material is based upon work supported under a National Science
# Foundation Graduate Research Fellowship. Any opinions, findings,
# conclusions or recommendations expressed in this publication are those of
# the author(s) and do not necessarily reflect the views of the National
# Science Foundation.

'''
Grid metascheduler for routing jobs to sites according to a ranking algorithm
that measures slot availability for running jobs. Job routing is performed
using a scheduling matrix that orders sites by rank. A periodic event re-scans
all sites to update the matrix. Dead sites (those with 0 total slots) are not
added into the scheduling matrix, but those sites are periodically re-scanned
to see if machines have been added.

It should be noted that this metascheduler only counts waiting and completed
jobs. A job is only "waiting" if it has not STARTED on the site to which it
has been matched. After a resubmission delay, jobs that are still waiting
will be canceled from the original site and re-submitted (likely to a new
site). Once a job has STARTED on a site, the metascheduler no longer tracks
it. THUS, THE RUNNING AND COMPLETED COUNTS FROM THE METASCHEDULER ARE
*ALWAYS* ZERO!
'''

import job_model, scheduler
from core_common import SM_WAITING

DEFAULT_POLLING_INTERVAL = 300
DEFAULT_RESUBMIT_DELAY = 3600


class Metascheduler(scheduler.Scheduler):
   '''
   Simple metascheduler: sends jobs to the site with the lowest projected
   waiting time, based on a ranking algorithm. Sites with at least one free
   core are always favored over sites where all machines are utilized. If
   jobs fail to start on the target site within a specified time period, then
   the job submission will be canceled on the original target site, and the
   job will be re-submitted to a new site.
   '''
   def __init__(self, simobj, polling_interval=DEFAULT_POLLING_INTERVAL, \
                name='Metascheduler', tag='', \
		resubmit_delay=DEFAULT_RESUBMIT_DELAY, **kwds):
      '''
      @param simobj: Reference to the simulator object
      @param polling_interval: Polling interval for updating the scheduling
                               matrix
      @type polling_interval: number
      @param name: Name of the metascheduler
      @type name: str
      @param tag: Optional scheduler tag
      @type tag: str
      @param resubmit_delay: Resubmission delay
      @type resubmit_delay: number
      @param kwds: Scheduler extra data
      '''
      scheduler.Scheduler.__init__(self, simobj, name, tag, **kwds)
      self.sitemap = {}
      self.sitedepth = {}
      self.sched_matrix = [[]]
      self.nanny = []
      self.dead_sites = {}
      self.max_size = 0
      self.interval = polling_interval
      self.resubmit_delay = resubmit_delay
      self.start_time = simobj.get_time()
      self.last_sched_run = self.start_time
      self.check_schedule()
   #
   def get_free_count(self):
      '''
      Returns the number of *sites* that had at least one free CPU core at
      the last matrix update
      '''
      return len(self.sched_matrix[0])
   def claim_slot(self, machine):
      '''
      Does nothing and returns False. This method is not used in this
      implementation because the metascheduler does not manage machines
      directly.

      @rtype: bool
      @return: False
      '''
      return False
   def free_slot(self, machine):
      '''
      Does nothing in this implementation
      '''
      pass
   def pick_slot(self, job):
      '''
      Does nothing and returns None
      '''
      return None
   def start_job(self, job, machine):
      '''
      Does nothing in this implementation
      '''
      pass
   def mark_complete(self, machine, job):
      '''
      Does nothing in this implementation
      '''
      pass
   def job_done(self, machine, job):
      '''
      Does nothing in this implementation
      '''
      pass
   def check_schedule(self):
      '''
      Determines if a matrix update event needs to be scheduled, and adds
      the matrix update event if necessary. Matrix updates are needed as
      long as jobs that have been submitted through the metascheduler have
      not yet started. To reduce the total number of simulator events, and
      thereby increase simulation speed, the metascheduler is capable of
      suspending itself when there are no jobs waiting.

      @rtype: bool
      @return: True iff a new matrix update has been added
      '''
      result = False
      if not self.event_pending():
         # The metascheduler needs to keep running as long as jobs are being
	 # watched by the nanny.
	 need = (self.get_waiting_count() > 0)
         if need:
	    cur_time = self.sim.get_time()
	    adjusted = self.last_sched_run - self.start_time
	    offset = self.interval - (adjusted % self.interval)
	    when = cur_time + offset
	    self.add_scheduler_event(when)
	    result = True
      return result
   def add_target(self, site):
      '''
      Adds a target site to the metascheduler. If the site has at least one
      CPU core, then the site is added to the scheduling matrix. Otherwise,
      the site will be added to the dead sites list and periodically
      re-checked to see if CPU cores have been added. Sites may be added to
      the metascheduler only once, and all site names must be unique, or an
      Exception will be raised.

      @param site: Site to add to the metascheduler
      '''
      name = site.name
      if (name in self.sitemap) or (name in self.dead_sites):
         raise Exception('Site names must be unique')
      else:
         total = site.get_cpu_count()
	 if total > 0:
            qd = site.get_waiting_count()
            self.sitemap[name] = site
	    self.set_site_matrix(name, qd)
	 else:
	    self.dead_sites[name] = site
   def remove_target(self, site):
      '''
      Remove a target site from the metascheduler. The site must be present
      either in the scheduling matrix or on the dead sites list, or an
      Exception will occur.

      @param site: Site to remove from the metascheduler
      '''
      name = site.name
      if name in self.sitemap:
         del self.sitemap[name]
	 self.set_site_matrix(name, -1)
      elif name in self.dead_sites:
         del self.dead_sites[name]
      else:
         raise KeyError('No key %s in sitemap or dead_sites' % name)
   #
   def rank_site(self, site):
      '''
      Computes the ranking for a site, so that the site can be placed into
      the proper scheduling matrix level. All sites with at least one free
      core have a rank of zero. Sites without free cores have a rank of one
      plus the integer result of computing the ratio of waiting jobs to
      total CPU core count. Sites without any CPU cores are assigned negative
      ranks.

      @param site: Site to be ranked

      @rtype: int
      @return: Site ranking (if non-negative). If a negative value is
      returned, then the site has no CPU cores.
      '''
      total = site.get_cpu_count()
      free = site.get_idle_count()
      waiting = site.get_waiting_count()
      rank = -1
      if total == 0:
         pass   # Negative rank == dead site
      elif free > 0:
         rank = 0
      else:
         rank = int(waiting / total) + 1
      return rank
   #
   def set_site_matrix(self, name, depth):
      '''
      Set the depth of a site in the site matrix. Even when the site depth
      does not change from its present value, this method will remove the site
      from the site matrix and then re-add it to the end of the row at the
      specified depth level. Since jobs are always submitted to the site at
      the beginning of the lowest-depth row, this procedure has the effect of
      load-balancing between sites.

      A negative depth will cause a site to be removed from the active site
      depth lists.

      @param name: Name of the site
      @type name: str
      @param depth: New site depth
      @type depth: int
      '''
      for n in xrange(self.max_size, depth):
         self.sched_matrix.append([])
	 self.max_size += 1
      if name in self.sitedepth:
         oldlevel = self.sitedepth[name]
	 self.sched_matrix[oldlevel].remove(name)
      if depth >= 0:
         self.sched_matrix[depth].append(name)
	 self.sitedepth[name] = depth
      else:
         if name in self.sitedepth:
	    del self.sitedepth[name]
   #
   def schedule(self, time, simobj):
      '''
      Periodically invoked method to adjust the scheduling matrix, check for
      dead sites, check to see if CPUs have been added to dead sites, and
      check to see that previously submitted jobs have been started. This
      routine is activated by a simulator event that is set by the
      check_schedule() method.

      @param time: Current simulated time
      @type time: number
      @param simobj: Reference to the simulator instance

      @return: scheduler update result
      '''
      self.last_sched_run = time
      for name in self.sitemap.keys():
         site = self.sitemap[name]
         rank = self.rank_site(site)
	 if rank >= 0:
	    if (name in self.sitedepth) and (self.sitedepth[name] == rank):
	       # Don't re-balance the list at the same depth, except when jobs
	       # are submitted.
	       pass
	    else:
	       self.set_site_matrix(name, rank)
	 else:
	    # Site has no CPUs (all targets dead)
	    self.remove_target(site)
	    self.dead_sites[name] = site
      #
      # Check dead list to see if any sites there have gained targets
      for name in self.dead_sites.keys()[:]:
         site = self.dead_sites[name]
         if site.get_cpu_count() > 0:
	    self.remove_target(site)
	    self.add_target(site)
      #
      # Check jobs on the nanny list to see if they started. Cancel and
      # re-submit jobs that exceed the wait limit.
      for job in self.nanny[:]:
         if job.running or job.complete:
	    self.nanny.remove(job)
            self.adjust_metric(SM_WAITING, -1)
	 else:
	    lag = time - job.submit_time
	    if lag > self.resubmit_delay:
	       job.sched.cancel_job(job)
	       job.submit_time = -1
	       job.sched = None
	       self.nanny.remove(job)
	       self.adjust_metric(SM_WAITING, -1)
	       self.submit_job(job)
      #
      self.check_schedule()
      return self.get_update()
   #
   def submit_job(self, job):
      '''
      Submits a job to the lowest-ranked site in the scheduling matrix. The
      job will be added to the nanny list so that it can be monitored to
      ensure that it starts before the resubmission interval elapses. After
      submission, the site position is adjusted in the scheduling matrix, so
      that load-balancing between sites may be effected even when the site
      depth does not change.

      @param job: Job to be submitted

      @return: the result of submitting the job to the site
      '''
      target_site = ''
      # Always pick the first site among the lowest-ranked
      for sitelist in self.sched_matrix:
         if sitelist != []:
	    target_site = sitelist[0]
	    break
      site = self.sitemap[target_site]
      result = site.submit_job(job)
      if not (job.running or job.complete):
         self.nanny.append(job)
	 self.adjust_metric(SM_WAITING, 1)
      rank = self.rank_site(site)
      self.set_site_matrix(target_site, rank)
      self.check_schedule()
      return result
#
